package com.sunwhite.algorithm.sort;

/** 冒泡排序算法 */

public class BubbleSort {

  public static void main(String[] args) {
    //
    int[] arr = new int[] {1, 8, 2, 6, 3, 9, 0, 5, 3, 2, 1, 89, 34, 23};
    BubbleSort bubbleSort = new BubbleSort();
    int[] sort = bubbleSort.sort(arr);
    for (int i : sort) {
      //
      System.out.print(i + ",");
    }
  }

  /**
   * 升序排序算法
   *1.将一串无序数字共有n个进行排序
   *2.将两个相邻的数组进行比较，左边数字大于右边数字则将两数调换位置，以此类推。
   *3.每一遍比较过后，这个数的最后一个位置将是次数组中最大的数字。
   *4.所以一共需要循环的次数为n-1次，因为最后n-1个数字确定过后，最后一个也确定了。
   *5.循环比较的次数，每次都需要减去已经确定的数字，就是已经循环的次数。
   *
   * 总结：所以冒泡排序算法最大的算法复杂度为n2，最小的算法复杂度为n,平均算法复杂度为log(n)
   *
   *
   * @param arr
   * @return
   */
  public int[] sort(int[] arr) {
    int count = 0;
    for (int i = 1; i < arr.length; i++) {
      // 冒泡排序算法
      for (int j = 0; j < arr.length - i; j++) {
        if (arr[j] > arr[j + 1]) {
          int a = arr[j + 1];
          arr[j + 1] = arr[j];
          arr[j] = a;
          count++;
        }
      }
    }
    System.out.println("数组的长度为：" + arr.length + ",复杂度为：" + count);
    return arr;
  }
}
